package com.lfg.leetcode.leetcode100;

import java.util.HashSet;
import java.util.Set;

/*

          Ø r a b b b i t
        Ø 1 1 1 1 1 1 1 1
        r 0 1 1 1 1 1 1 1
        a 0 0 1 1 1 1 1 1
        b 0 0 0 1 2 3 3 3
        b 0 0 0 0 1 3 3 3
        i 0 0 0 0 0 0 3 3
        t 0 0 0 0 0 0 0 3
*/

public class No115numDistinct {

    public static void main(String[] args) {
        int ret = numDistinct2("adbdadeecadeadeccaeaabdabdbcdabddddabcaaadbabaaedeeddeaeebcdeabcaaaeeaeeabcddcebddebeebedaecccbdcbcedbdaeaedcdebeecdaaedaacadbdccabddaddacdddc", "bcddceeeebecbc");
        System.out.println("[" + ret + "]");
    }


    public static int numDistinct(String s, String t) {

        if (null == t || null == s || t.length() > s.length()) {
            return 0;
        }

        int tLength = t.length();
        StringBuilder sb = new StringBuilder(s.length());
        Set<Character> sets = new HashSet<Character>(tLength);
        for (int i = 0; i < tLength; i++) {
            sets.add(t.charAt(i));
        }
        for (int i = 0; i < s.length(); i++) {
            if (sets.contains(s.charAt(i))) {
                sb.append(s.charAt(i));
            }
        }

        if (tLength > sb.length()) {
            return 0;
        }

        int sLength = sb.length();
        int[][] dp = new int[sLength + 1][tLength + 1];
        for (int i = sLength; i >= 0; i--) {
            dp[i][0] = 1;
        }
        for (int i = 1; i <= sLength; i++) {
            for (int j = 1; j <= tLength; j++) {
                if (sb.charAt(i - 1) == t.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
                } else {
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
        return dp[sLength][tLength];
    }


    public static int numDistinct2(String s, String t) {
        if (null == t || null == s || t.length() > s.length()) {
            return 0;
        }
        StringBuilder sb = new StringBuilder(s.length());
        Set<Character> sets = new HashSet<Character>(t.length());
        for (int i = 0; i < t.length(); i++) {
            sets.add(t.charAt(i));
        }
        for (int i = 0; i < s.length(); i++) {
            if (sets.contains(s.charAt(i))) {
                sb.append(s.charAt(i));
            }
        }
        return numDistinct(sb.toString(), 0, sb.length(), t, 0, t.length());
    }

    public static int numDistinct(String s, int sIndex, int sLength, String t, int tIndex, int tLength) {
        int ret = 0;
        if (tIndex >= tLength) {
            return 1;
        }
        if (sIndex >= sLength) {
            return 0;
        }
        if (sLength - sIndex < tLength - tIndex) {
            return 0;
        }

        if (s.charAt(sIndex) == t.charAt(tIndex)) {
            ret += numDistinct(s, sIndex + 1, sLength, t, tIndex + 1, tLength);
        }
        ret += numDistinct(s, sIndex + 1, sLength, t, tIndex, tLength);
        return ret;
    }
}
